# coding: utf-8
# 插入排序实现

# 使用嵌套的if-else模仿pattern match
insert = lambda x,array: \
    [x] if len(array)<1 \
    else(
        [x]+array if x<=array[0] else [array[0]]+insert(x,array[1:])
        )

insertion_sort = lambda array: \
    array if len(array)<1 \
    else insert(array[0],insertion_sort(array[1:]))

# 非递归写法
def insertion_sort2(lst):
    lstLen = len(lst)
    # 遍历 0..(lstLen-1)
    for i in range(0,lstLen):
        # 从后往前插入 i..0
        for j in range(i,0,-1):
            if lst[j]<lst[j-1]:
                # 交换左右元素
                lst[j],lst[j-1]=lst[j-1],lst[j]
            else:
                break
    
# 非递归单指针写法（指针可以回退）
# 这个版本非常适合链表实现，操作简单
def insertion_sort3(lst):
    lstLen = len(lst)
    # 遍历 0..(lstLen-1)
    for i in range(0,lstLen):
        #如果有逆序对，就回退指针，直到没有逆序对
        while i>0 and lst[i]<lst[i-1]:
            # 交换左右元素
            lst[i],lst[i-1]=lst[i-1],lst[i]
            i-=1

def shellSort(lst):
    lstLen=len(lst)
    #希尔排序中的增量gap，一开始为长度的一半
    gap=int(lstLen/2)
    while gap>0:
        #执行指针回退的插入排序
        for i in range(gap,lstLen):
            #如果有逆序对，就回退指针，直到没有逆序对
            while i>0 and lst[i]<lst[i-gap]:
                # 交换左右元素
                lst[i],lst[i-gap]=lst[i-gap],lst[i]
                i-=gap
        #按gap/2进行增量递减
        gap=int(gap/2)

lst = [1,11,2,22,3,33,1,2,3]
lstLen = len(lst)

print("origin:",lst)

print("sort1:",insertion_sort(lst))

insertion_sort2(lst)
print("sort2:",lst)

lst = [1,11,2,22,3,33,1,2,3]
lstLen = len(lst)
insertion_sort3(lst)
print("sort3:",lst)

lst = [1,11,2,22,3,33,1,2,3,-1,-2,-3]
lstLen = len(lst)
shellSort(lst)
print("shellSort:",lst)
